package org.example.algorithm.heap;

/**
 * 构建一个最小堆，大小为k，则堆顶元素即为所求
 */
public class FindKthLargestUseMinHeap {

    public int findKthLargest(int[] nums, int k) {
        //最后一个非叶子节点
        int lastNoLeaf = (k - 2) / 2;
        for (int i=lastNoLeaf;i>=0;i--) {
            siftDown(nums, i, k);
        }
        for (int i=k;i<nums.length;i++) {
            if (nums[i] > nums[0]) {
                nums[0] = nums[i];
                siftDown(nums, 0, k);
            }
        }
        return nums[0];
    }

    public void siftDown(int[] nums, int pos, int size) {
        int left = 2 * pos + 1;
        int right = 2 * pos + 2;
        int minPos = pos;
        if (left < size && nums[left] < nums[minPos]) {
            minPos = left;
        }
        if (right < size && nums[right] < nums[minPos]) {
            minPos = right;
        }
        if (minPos != pos) {
            swapNum(nums, pos, minPos);
            siftDown(nums, minPos, size);
        }
    }

    private void swapNum(int[] nums, int from, int to) {
        int temp = nums[from];
        nums[from] = nums[to];
        nums[to] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {7,6,5,4,3,2,1};
        FindKthLargestUseMinHeap findHeap = new FindKthLargestUseMinHeap();
        int res = findHeap.findKthLargest(arr, 4);
        System.out.println(res);
    }
}
